package java学习.算法.排序;

import java.util.*;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/6/21 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 最小的K个数 {

    /*
    给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。
    例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。

    要求：空间复杂度 O(n) ，时间复杂度 O(nlogn)
     */

    public static void main(String[] args) {
//        int[] arr = {4,5,1,6,2,7,3,8};
        int[] arr = {0, 1, 2, 1, 2};
        Arrays.sort(arr);
        System.out.println(GetLeastNumbers_Solution3(arr, 4));

    }

    public static ArrayList<Integer> GetLeastNumbers_Solution1(int[] input, int k) {
        int n = input.length;
//         Set<Integer> set = new HashSet<>();
//        for (int i = 0; i < n; i++) {
//            set.add(input[i]);
//        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(input[i]);
        }
        ArrayList<Integer> result = new ArrayList<>();

        for (int i = 0; i < k; i++) {
            result.add(list.get(i));
        }
        return result;
    }

    public static ArrayList<Integer> GetLeastNumbers_Solution2(int[] input, int k) {
//        直接排序。
        Arrays.sort(input);
        ArrayList<Integer> result = new ArrayList<>();

        for (int i = 0; i < k; i++) {
            result.add(input[i]);
        }
        return result;
    }

//    法2 优先级队列： 大根堆。
//   因为只要找到 最小的K个数 ， 就设队列为k个大小，每次遇到更小的数，就将队列的数更新。

    public static ArrayList<Integer> GetLeastNumbers_Solution3(int [] input, int k) {
        ArrayList<Integer> result =  new ArrayList<>();
        //排除特殊情况
        if(k == 0 || input.length == 0)
            return result;
        Queue<Integer> queue  = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });

//         先在队列中放入k个元素
        for (int i = 0; i<k;i++){
            queue.offer(input[i]);
        }
//        依次遍历 input数组，若出现比大根堆 堆顶元素 小的值，则替换。
        for (int j = k; j < input.length; j++) {
            if (queue.peek()>input[j]){
                queue.poll();
                queue.offer(input[j]);
            }
        }

//        最后将大根堆的值放入result
        for (int i = 0; i < k; i++) {
            result.add(queue.poll());
        }
        return result;
    }

        public ArrayList<Integer> GetLeastNumbers_Solution4(int [] input, int k) {
            ArrayList<Integer> res = new ArrayList<Integer>();
            //排除特殊情况
            if(k == 0 || input.length == 0) {
                return res;
            }
            //大根堆
            PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2)->o2.compareTo(o1));
            //构建一个k个大小的堆
            for(int i = 0; i < k; i++)
                q.offer(input[i]);
            for(int i = k; i < input.length; i++){
                //较小元素入堆
                if(q.peek() > input[i]){
                    q.poll();
                    q.offer(input[i]);
                }
            }
            //堆中元素取出入数组
            for(int i = 0; i < k; i++) {
                res.add(q.poll());
            }
            return res;
        }



}
